package com.kaifamiao.base.exam20210925;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;


/**
 * @author lucien-ma
 * @date 2021/9/25
 * @apiNote
 */
public class QuickSort {

    private QuickSort(){}

    public static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (l >= r)
            return;
        int p = partition(arr, l, r);
        sort(arr, l, p - 1);
        sort(arr, p + 1, r);
    }

    /**
     * 以数组的第一位为基准点，
     * 将小玉基准点的所有元素，放到左边，反之放到右边
     * 返回基准点的索引
     * @param arr
     * @param l
     * @param r
     * @param <E>
     * @return
     */
    private static <E extends Comparable<E>> int partition(E[] arr, int l, int r) {
        // arr[l+1...j] < v ;  arr[j+1...i-1] >= v
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i].compareTo(arr[l]) < 0) {
                j++;
                swap(arr, i, j);
            }
        }
        swap(arr, l, j);
        return j;
    }

    /**
     * 交换位置
     * @param arr
     * @param i
     * @param j
     */
    private static <E> void swap(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    public static void main(String[] args){
        Student student1= new Student("艾斯", "10001", 20, '男');
        Student student2= new Student("萨博", "10002", 19, '男');
        Student student3= new Student("路飞", "10003", 18, '男');
        Student student4= new Student("路飞", "10004", 20, '男');
        Student student5= new Student("索隆", "10005", 21, '男');
        Student student6= new Student("山治", "10006", 22, '男');
        Student student7= new Student("娜美", "10007", 18, '女');
        Student[] students = {student1, student2, student3, student4, student5, student6, student7};

        sort(students);
        for (Student student : students) {
            System.out.println(student);
        }
    }
}

@Data
@AllArgsConstructor
@NoArgsConstructor
class Student implements Comparable<Student>{
    private String stuName; //学生姓名
    private String stuNo;  // 学号
    private Integer age;       // 年龄
    private Character gender; // 性别

    @Override
    public int compareTo(Student o) {
        if (this.stuName.equals(o.stuName)) {
            return this.stuNo.compareTo(o.stuNo);
        }
        return this.stuName.compareTo(o.stuName);
    }
}